package crossbreed.diff;
// Copyright (c) by Matthias Hertel, http://www.mathertel.de
// This work is licensed under a BSD style license. See http://www.mathertel.de/License.aspx

import java.util.ArrayList;
import java.util.Hashtable;

public class Diff implements IDiff
{
	public DiffItem[] diffText(String TextA, String TextB)
	{
		return (diffText(TextA, TextB, false, false, false));
	}

	public DiffItem[] diffText(String TextA, String TextB, boolean trimSpace,
			boolean ignoreSpace, boolean ignoreCase)
	{
		Hashtable<String, Integer> h = new Hashtable<String, Integer>(TextA.length() + TextB.length());
		DiffData DataA = new DiffData(diffCodes(TextA, h, trimSpace, ignoreSpace, ignoreCase));
		DiffData DataB = new DiffData(diffCodes(TextB, h, trimSpace, ignoreSpace, ignoreCase));
		h = null;

		int MAX = DataA.Length + DataB.Length + 1;
		int[] DownVector = new int[2 * MAX + 2];
		int[] UpVector = new int[2 * MAX + 2];

		lcs(DataA, 0, DataA.Length, DataB, 0, DataB.Length, DownVector, UpVector);

		optimize(DataA);
		optimize(DataB);
		return createDiffs(DataA, DataB);
	}

	private static void optimize(DiffData Data)
	{
		int StartPos = 0;
		int EndPos = 0;

		while (StartPos < Data.Length)
		{
			while ((StartPos < Data.Length) && (Data.modified[StartPos] == false))
				StartPos++;
			EndPos = StartPos;
			while ((EndPos < Data.Length) && (Data.modified[EndPos] == true))
				EndPos++;

			if ((EndPos < Data.Length) && (Data.data[StartPos] == Data.data[EndPos]))
			{
				Data.modified[StartPos] = false;
				Data.modified[EndPos] = true;
			}
			else
			{
				StartPos = EndPos;
			}
		}
	}

	private static int[] diffCodes(String aText, Hashtable<String, Integer> h, boolean trimSpace,
			boolean ignoreSpace, boolean ignoreCase)
	{
		String[] Lines;
		int[] Codes;
		int lastUsedCode = h.size();
		Object aCode;
		String s;

		aText = aText.replace("\r", "");
		Lines = aText.split("\n");
		Codes = new int[Lines.length];

		for (int i = 0; i < Lines.length; ++i)
		{
			s = Lines[i];

			if (trimSpace) s = s.trim();
			if (ignoreSpace) s = s.replaceAll("\\s+", " ");
			if (ignoreCase) s = s.toLowerCase();

			aCode = h.get(s);

			if (aCode == null)
			{
				lastUsedCode++;
				h.put(s, lastUsedCode);
				Codes[i] = lastUsedCode;
			}
			else
			{
				Codes[i] = (Integer) aCode;
			}
		}

		return (Codes);
	}

	private static Point sms(DiffData DataA, int LowerA, int UpperA, DiffData DataB, int LowerB,
			int UpperB, int[] DownVector, int[] UpVector)
	{
		Point ret = new Point();
		int MAX = DataA.Length + DataB.Length + 1;
		int DownK = LowerA - LowerB;
		int UpK = UpperA - UpperB;
		int Delta = (UpperA - LowerA) - (UpperB - LowerB);
		boolean oddDelta = (Delta & 1) != 0;

		int DownOffset = MAX - DownK;
		int UpOffset = MAX - UpK;

		int MaxD = ((UpperA - LowerA + UpperB - LowerB) / 2) + 1;

		DownVector[DownOffset + DownK + 1] = LowerA;
		UpVector[UpOffset + UpK - 1] = UpperA;

		for (int D = 0; D <= MaxD; D++)
		{
			for (int k = DownK - D; k <= DownK + D; k += 2)
			{
				int x, y;
				if (k == DownK - D)
				{
					x = DownVector[DownOffset + k + 1];
				}
				else
				{
					x = DownVector[DownOffset + k - 1] + 1;
					if ((k < DownK + D) && (DownVector[DownOffset + k + 1] >= x)) x = DownVector[DownOffset
							+ k + 1];
				}
				y = x - k;

				while ((x < UpperA) && (y < UpperB) && (DataA.data[x] == DataB.data[y]))
				{
					x++;
					y++;
				}

				DownVector[DownOffset + k] = x;

				if (oddDelta && (UpK - D < k) && (k < UpK + D))
				{
					if (UpVector[UpOffset + k] <= DownVector[DownOffset + k])
					{
						ret.x = DownVector[DownOffset + k];
						ret.y = DownVector[DownOffset + k] - k;
						return (ret);
					}
				}
			}

			for (int k = UpK - D; k <= UpK + D; k += 2)
			{
				int x, y;

				if (k == UpK + D)
				{
					x = UpVector[UpOffset + k - 1];
				}
				else
				{
					x = UpVector[UpOffset + k + 1] - 1;
					if ((k > UpK - D) && (UpVector[UpOffset + k - 1] < x)) x = UpVector[UpOffset + k - 1];
				}

				y = x - k;

				while ((x > LowerA) && (y > LowerB) && (DataA.data[x - 1] == DataB.data[y - 1]))
				{
					x--;
					y--;
				}

				UpVector[UpOffset + k] = x;

				if (!oddDelta && (DownK - D <= k) && (k <= DownK + D))
				{
					if (UpVector[UpOffset + k] <= DownVector[DownOffset + k])
					{
						ret.x = DownVector[DownOffset + k];
						ret.y = DownVector[DownOffset + k] - k;
						return (ret);
					}
				}
			}
		}

		return null;
	}

	private static void lcs(DiffData DataA, int LowerA, int UpperA, DiffData DataB, int LowerB,
			int UpperB, int[] DownVector, int[] UpVector)
	{
		while (LowerA < UpperA && LowerB < UpperB && DataA.data[LowerA] == DataB.data[LowerB])
		{
			LowerA++;
			LowerB++;
		}

		while (LowerA < UpperA && LowerB < UpperB && DataA.data[UpperA - 1] == DataB.data[UpperB - 1])
		{
			--UpperA;
			--UpperB;
		}

		if (LowerA == UpperA)
		{
			while (LowerB < UpperB)
				DataB.modified[LowerB++] = true;
		}
		else if (LowerB == UpperB)
		{
			while (LowerA < UpperA)
				DataA.modified[LowerA++] = true;
		}
		else
		{
			Point smsrd = sms(DataA, LowerA, UpperA, DataB, LowerB, UpperB, DownVector, UpVector);
			lcs(DataA, LowerA, smsrd.x, DataB, LowerB, smsrd.y, DownVector, UpVector);
			lcs(DataA, smsrd.x, UpperA, DataB, smsrd.y, UpperB, DownVector, UpVector);
		}
	}

	private static DiffItem[] createDiffs(DiffData DataA, DiffData DataB)
	{
		ArrayList<DiffItem> a = new ArrayList<DiffItem>();
		DiffItem aItem;

		int StartA, StartB;
		int LineA, LineB;

		LineA = 0;
		LineB = 0;
		while (LineA < DataA.Length || LineB < DataB.Length)
		{
			if ((LineA < DataA.Length) && (!DataA.modified[LineA]) && (LineB < DataB.Length)
					&& (!DataB.modified[LineB]))
			{
				LineA++;
				LineB++;

			}
			else
			{
				StartA = LineA;
				StartB = LineB;

				while (LineA < DataA.Length && (LineB >= DataB.Length || DataA.modified[LineA]))
					LineA++;

				while (LineB < DataB.Length && (LineA >= DataA.Length || DataB.modified[LineB]))
					LineB++;

				if ((StartA < LineA) || (StartB < LineB))
				{
					aItem = new DiffItem();
					aItem.StartA = StartA;
					aItem.StartB = StartB;
					aItem.deletedA = LineA - StartA;
					aItem.insertedB = LineB - StartB;
					a.add(aItem);
				}
			}
		}

		DiffItem[] result = new DiffItem[a.size()];
		return a.toArray(result);
	}
}